package cn.cxq.learning.tree;

import org.junit.jupiter.api.Test;

/**
 * 剑指offer
 * 重建二叉树
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：1195693
 * 本题知识点： 树 dfs 数组
 * 算法知识视频讲解
 * 题目描述
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 * 示例1
 * 输入
 * 复制
 * [1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
 * 返回值
 * 复制
 * {1,2,5,3,4,6,7}
 */
public class ReConstructBinaryTree {

    int cur = 0;


    @Test
    public void test() {
        TreeNode treeNode = reConstructBinaryTree(new int[]{1, 2, 3, 4, 5, 6, 7}, new int[]{3, 2, 4, 1, 6, 5, 7});
        System.out.println();
    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {

        if (pre.length == 0) {
            return null;
        }

        TreeNode root = new TreeNode(pre[0]);
        cur = 1;

        for (int i = 0; i < in.length; i++) {
            if (pre[0] == in[i]) {
                reConstructLeftTree(root, pre, in, i - 1, 0);
                reConstructRightTree(root, pre, in, i + 1, in.length - 1);
                break;
            }
        }

        return root;
    }

    private void reConstructLeftTree(TreeNode node, int[] pre, int[] in, int rightBound, int leftBound) {
        if (leftBound > rightBound || cur == pre.length) {
            return;
        }
        for (int i = leftBound; i <= rightBound; i++) {
            if (pre[cur] == in[i]) {
                node.left = new TreeNode(pre[cur]);
                cur++;
                reConstructLeftTree(node.left, pre, in, i - 1, leftBound);
                reConstructRightTree(node.left, pre, in, i + 1, rightBound);
                break;
            }
        }
    }

    private void reConstructRightTree(TreeNode node, int[] pre, int[] in, int leftBound, int rightBound) {
        if (leftBound > rightBound || cur == pre.length) {
            return;
        }
        for (int i = leftBound; i <= rightBound; i++) {
            if (pre[cur] == in[i]) {
                node.right = new TreeNode(pre[cur]);
                cur++;
                reConstructLeftTree(node.right, pre, in, i - 1, leftBound);
                reConstructRightTree(node.right, pre, in, i + 1, rightBound);
                break;
            }
        }
    }
}
